package cn.edu.zufe.mjt.dp;

import java.util.Arrays;

/**
 * 动态规划 —— 最大字段和问题
 * 给定一个整数序列 a1,a2,…,an，其中n为整数序列的长度。
 * 请你计算出该序列的最大子段和，即从该序列中选出一个连续的子序列，使得子席列的和最大。
 * 请注意，子序列的长度可以为 1，且可以是整个席列。
 */
public class MaxFieldSum {
    public static void main(String[] args) {
        int[] a = {4, -1, 2, -3, 5, -2, 3};
        System.out.println(maxFieldSum(a));
    }

    /**
     * 还是数学推导五步法
     * ① 构造集合:从具体例子出发，列出所有情况
     * ② 寻找等式:根据集合元素中上一个位置的取值进行集合划分
     * ③ 集合映射:去掉集合元素的最后一个元素，集合映射为子问题形式
     * ④ 推广得到递推式
     * ⑤ 列举边界情况
     * 枚举 n = 3 的情况 假设 a = {4,-1,2}
     * 一、列举所有情况： {4,-1,2} {4,-1} {4} {-1,2} {-1} {2}  命名为 D 集合
     * 由于是序列型的集合，那么可以按照元素中最后一个数相等的情况进行划分
     * 则有 D[1] = {4}, D[2] = {{4,-1},{-1}}, D[3] = {{4,-1,2},{-1,2},{2}}。 D[i]就是以a[i]结尾的子序列集合。
     * 要求的答案？这里就不是集合的大小了（求方案数的时候是集合的大小），而是集合内元素和的最大值。
     * 那就定义答案，令 MaxSum[i] = max(Σx|x∈S)(S ∈ D[i])
     * 三、探索转移： 对于 D[3]，尝试把最后一个相同的结尾去掉之后得到 {{4，-1},{-1},{∅}}。可以看到这里 D[3] 与 D[2] 有一个空集的差异。
     * 可以这么理解， 以 a[3] 结尾的子序列去掉最后一个元素之后，肯定会包含全部以 a[2] 结尾的子序列，于是可以跟 D[2] 相关联。
     * 于是可以得出 D[3] = {{x,2} | x∈D[2] ∪ {∅}}，这个式子表示，D[3] 是 以 x 和 2 组合而来的集合，其中 x 取自 D[2] 或者空集。 这个式子是推导出转移方程的关键。
     * 带入答案中 MaxSum[3] = max(Σx|x∈S)(S ∈ D[3]) = max(Σx|x∈S)(S ∈ {{x,2} | x∈D[2] ∪ {∅}})
     * 因为 S 一定是包含 2，那么 等式可化简为 max(Σ(x + 2)|x∈S)(S ∈ {D[2],∅})。 2 可以提出来 于是 MaxSum[3] = max(Σx|x∈S)(S ∈ {D[2],∅})+ 2
     * 而集合 S 属于两个不同的集合 D[2] 和 {∅}，那么又可以拆出来分别 max(Σx|x∈S)(S ∈ D[2]) 和 max(Σx|x∈S)(S ∈ {∅})。再求max，于是有
     * MaxSum[3] = max(max(Σx|x∈S)(S ∈ D[2]), max(Σx|x∈S)(S ∈ {∅})) + 2
     * 此时对于外层 max 的第一项，根据 MaxSum[i] 的定义就可以得到 MaxSum[3] = max(MaxSum[2], 0) + 2，MaxSum[3] 此时已经与 MaxSum[2] 相关联。 空集最大值可以看作 0。
     * 于是 MaxSum[3] 和 MaxSum[2] 的转移方程就是 MaxSum[3] = max(MaxSum[2], 0) + 2
     * 四、推广得到递推式 MaxSum[i] = max(MaxSum[i-1], 0) + a[i]，其中 i > 1。
     * 边界为数组长度为 1 的情况，MaxSum[1] = a[1]。
     * <br>
     * 如何理解递推式 MaxSum[i] = max(MaxSum[i-1], 0) + a[i]？
     * 1.以i为结尾的子数组一定包含ai
     * 2.最优解可能有两种情况:
     * 2.1 a[i]
     * 2.2 (a[x]+a[x+1]+...+a[i-1]) + a[i]
     * 3.对于2.2的情况:一定是以i-1为结尾的所有子数组中找最大值出来(贪心),这个最大值就是MaxSum(i-1)
     */
    public static int maxFieldSum(int[] a) {
        int[] maxSum = new int[a.length];
        maxSum[0] = Math.max(0, a[0]);
        for (int i = 1; i < a.length; i++) {
            maxSum[i] = Math.max(maxSum[i - 1], 0) + a[i];
        }
        return Arrays.stream(maxSum).max().orElse(0);
    }
}
